home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / networking / ip / ka9q / alpha.arc / IPROUTE.C < prev    next >
C/C++ Source or Header  |  1988-07-21  |  16KB  |  632 lines

  1. /* Lower half of IP, consisting of gateway routines
  2.  * Includes routing and options processing code
  3.  */
  4. #include "global.h"
  5. #include "mbuf.h"
  6. #include "internet.h"
  7. #include "timer.h"
  8. #include "netuser.h"
  9. #include "ip.h"
  10. #include "icmp.h"
  11. #include "iface.h"
  12. #include "trace.h"
  13.  
  14. struct route *routes[32][NROUTE];    /* Routing table */
  15. struct route r_default;            /* Default route entry */
  16.  
  17. int32 ip_addr;
  18. struct ip_stats ip_stats;
  19.  
  20. #ifndef    GWONLY
  21. struct mbuf *loopq;    /* Queue for loopback packets */
  22. #endif
  23.  
  24. /* Route an IP datagram. This is the "hopper" through which all IP datagrams,
  25.  * coming or going, must pass.
  26.  *
  27.  * "rxbroadcast" is set to indicate that the packet came in on a subnet
  28.  * broadcast. The router will kick the packet upstairs regardless of the
  29.  * IP destination address.
  30.  */
  31. int
  32. ip_route(bp,rxbroadcast)
  33. struct mbuf *bp;
  34. char rxbroadcast;    /* True if packet had link broadcast address */
  35. {
  36.     struct mbuf *htonip();
  37.     void ip_recv();
  38.     struct ip ip;            /* IP header being processed */
  39.     int16 ip_len;            /* IP header length */
  40.     int16 length;            /* Length of data portion */
  41.     int32 gateway;            /* Gateway IP address */
  42.     register struct route *rp;    /* Route table entry */
  43.     struct interface *iface;    /* Output interface, possibly forwarded */
  44.     struct route *rt_lookup();
  45.     int16 offset;            /* Offset into current fragment */
  46.     int16 mf_flag;            /* Original datagram MF flag */
  47.     int strict = 0;            /* Strict source routing flag */
  48.     char precedence;        /* Extracted from tos field */
  49.     char delay;
  50.     char throughput;
  51.     char reliability;
  52.     int16 opt_len;        /* Length of current option */
  53.     char *opt;        /* -> beginning of current option */
  54.     char *ptr;        /* -> pointer field in source route fields */
  55.     struct mbuf *tbp;
  56.  
  57.     ip_stats.total++;
  58.     if(len_mbuf(bp) < IPLEN){
  59.         /* The packet is shorter than a legal IP header */
  60.         ip_stats.runt++;
  61.         free_p(bp);
  62.         return -1;
  63.     }
  64.     /* Sneak a peek at the IP header's IHL field to find its length */
  65.     ip_len = (bp->data[0] & 0xf) << 2;
  66.     if(ip_len < IPLEN){
  67.         /* The IP header length field is too small */
  68.         ip_stats.length++;
  69.         free_p(bp);
  70.         return -1;
  71.     }
  72.     if(cksum(NULLHEADER,bp,ip_len) != 0){
  73.         /* Bad IP header checksum; discard */
  74.         ip_stats.checksum++;
  75.         free_p(bp);
  76.         return -1;
  77.     }
  78.     /* Extract IP header */
  79.     ntohip(&ip,&bp);
  80.  
  81.     if(ip.version != IPVERSION){
  82.         /* We can't handle this version of IP */
  83.         ip_stats.version++;
  84.         free_p(bp);
  85.         return -1;
  86.     }
  87.     /* Trim data segment if necessary. */
  88.     length = ip.length - ip_len;    /* Length of data portion */
  89.     trim_mbuf(&bp,length);    
  90.                 
  91.     /* Process options, if any. Also compute length of secondary IP
  92.      * header in case fragmentation is needed later
  93.      */
  94.     strict = 0;
  95.     for(opt = ip.options; opt < &ip.options[ip.optlen];opt += opt_len){
  96.         int32 get32();
  97.  
  98.         /* Most options have a length field. If this is a EOL or NOOP,
  99.          * this (garbage) value won't be used
  100.          */
  101.         opt_len = uchar(opt[1]);
  102.  
  103.         switch(opt[0] & OPT_NUMBER){
  104.         case IP_EOL:
  105.             goto no_opt;    /* End of options list, we're done */
  106.         case IP_NOOP:
  107.             opt_len = 1;
  108.             break;        /* No operation, skip to next option */
  109.         case IP_SSROUTE:    /* Strict source route & record route */
  110.             strict = 1;    /* note fall-thru */
  111.         case IP_LSROUTE:    /* Loose source route & record route */
  112.             /* Source routes are ignored unless we're in the
  113.              * destination field
  114.              */
  115.             if(ip.dest != ip_addr)
  116.                 break;    /* Skip to next option */
  117.             if(uchar(opt[2]) >= opt_len){
  118.                 break;    /* Route exhausted; it's for us */
  119.             }
  120.             /* Put address for next hop into destination field,
  121.              * put our address into the route field, and bump
  122.              * the pointer
  123.              */
  124.             ptr = opt + uchar(opt[2]) - 1;
  125.             ip.dest = get32(ptr);
  126.             put32(ptr,ip_addr);
  127.             opt[2] += 4;
  128.             break;
  129.         case IP_RROUTE:    /* Record route */
  130.             if(uchar(opt[2]) >= opt_len){
  131.                 /* Route area exhausted; kick back an error */
  132.                 union icmp_args icmp_args;
  133.  
  134.                 icmp_args.pointer = IPLEN + opt - ip.options;
  135.                 icmp_output(&ip,bp,PARAM_PROB,0,&icmp_args);
  136.                 free_p(bp);
  137.                 return -1;
  138.             }
  139.             /* Add our address to the route */
  140.             ptr = opt + uchar(opt[2]) - 1;
  141.             ptr = put32(ptr,ip_addr);
  142.             opt[2] += 4;
  143.             break;
  144.         }
  145.     }
  146. no_opt:
  147.  
  148.     /* See if it's a broadcast or addressed to us, and kick it upstairs */
  149.     if(ip.dest == ip_addr || rxbroadcast){
  150. #ifdef    GWONLY
  151.     /* We're only a gateway, we have no host level protocols */
  152.         if(!rxbroadcast)
  153.             icmp_output(&ip,bp,DEST_UNREACH,PROT_UNREACH,(union icmp_args *)NULL);
  154.         free_p(bp);
  155. #else
  156.  
  157.         /* If this is a local loopback packet, place on the loopback
  158.          * queue for processing in the main loop. This prevents the
  159.          * infinite stack recursion and other problems that would
  160.          * otherwise occur when we talk to ourselves, e.g., with ftp
  161.          */
  162.         if(ip.source == ip_addr){
  163.             /* Put IP header back on */
  164.             if((tbp = htonip(&ip,bp)) == NULLBUF){
  165.                 free_p(bp);
  166.                 return -1;
  167.             }
  168.             /* Copy loopback packet into new buffer.
  169.              * This avoids an obscure problem with TCP which
  170.              * dups its outgoing data before transmission and
  171.              * then frees it when an ack comes, even though the
  172.              * receiver might not have actually read it yet
  173.              */
  174.             bp = copy_p(tbp,len_mbuf(tbp));
  175.             free_p(tbp);
  176.             if(bp == NULLBUF)
  177.                 return -1;
  178.             enqueue(&loopq,bp);
  179.         } else {
  180.             ip_recv(&ip,bp,rxbroadcast);
  181.         }
  182. #endif
  183.         return 0;
  184.     }
  185.  
  186.     /* Decrement TTL and discard if zero */
  187.     if(--ip.ttl == 0){
  188.         /* Send ICMP "Time Exceeded" message */
  189.         icmp_output(&ip,bp,TIME_EXCEED,0,NULLICMP);
  190.         free_p(bp);
  191.         return -1;
  192.     }
  193.     /* Look up target address in routing table */
  194.     if((rp = rt_lookup(ip.dest)) == NULLROUTE){
  195.         /* No route exists, return unreachable message */
  196.         icmp_output(&ip,bp,DEST_UNREACH,HOST_UNREACH,NULLICMP);
  197.         free_p(bp);
  198.         return -1;
  199.     }
  200.     /* Check for output forwarding and divert if necessary */
  201.     iface = rp->interface;
  202.     if(iface->forw != NULLIF)
  203.         iface = iface->forw;
  204.  
  205.     /* Find gateway; zero gateway in routing table means "send direct" */
  206.     if(rp->gateway == (int32)0)
  207.         gateway = ip.dest;
  208.     else
  209.         gateway = rp->gateway;
  210.  
  211.     if(strict && gateway != ip.dest){
  212.         /* Strict source routing requires a direct entry */
  213.         icmp_output(&ip,bp,DEST_UNREACH,ROUTE_FAIL,NULLICMP);
  214.         free_p(bp);
  215.         return -1;
  216.     }
  217.     precedence = PREC(ip.tos);
  218.     delay = ip.tos & DELAY;
  219.     throughput = ip.tos & THRUPUT;
  220.     reliability = ip.tos & RELIABILITY;
  221.  
  222.     if(ip.length <= iface->mtu){
  223.         /* Datagram smaller than interface MTU; put header
  224.          * back on and send normally
  225.          */
  226.         if((tbp = htonip(&ip,bp)) == NULLBUF){
  227.             free_p(bp);
  228.             return -1;
  229.         }
  230.         return (*iface->send)(tbp,iface,gateway,
  231.             precedence,delay,throughput,reliability);
  232.     }
  233.     /* Fragmentation needed */
  234.     if(ip.fl_offs & DF){
  235.         /* Don't Fragment set; return ICMP message and drop */
  236.         icmp_output(&ip,bp,DEST_UNREACH,FRAG_NEEDED,NULLICMP);
  237.         free_p(bp);
  238.         return -1;
  239.     }
  240.     /* Create fragments */
  241.     offset = (ip.fl_offs & F_OFFSET) << 3;
  242.     mf_flag = ip.fl_offs & MF;    /* Save original MF flag */
  243.     while(length != 0){        /* As long as there's data left */
  244.         int16 fragsize;        /* Size of this fragment's data */
  245.         struct mbuf *f_data;    /* Data portion of fragment */
  246.  
  247.         /* After the first fragment, should remove those
  248.          * options that aren't supposed to be copied on fragmentation
  249.          */
  250.         ip.fl_offs = offset >> 3;
  251.         if(length + ip_len <= iface->mtu){
  252.             /* Last fragment; send all that remains */
  253.             fragsize = length;
  254.             ip.fl_offs |= mf_flag;    /* Pass original MF flag */
  255.         } else {
  256.             /* More to come, so send multiple of 8 bytes */
  257.             fragsize = (iface->mtu - ip_len) & 0xfff8;
  258.             ip.fl_offs |= MF;
  259.         }
  260.         ip.length = fragsize + ip_len;
  261.  
  262.         /* Move the data fragment into a new, separate mbuf */
  263.         if((f_data = alloc_mbuf(fragsize)) == NULLBUF){
  264.             free_p(bp);
  265.             return -1;
  266.         }
  267.         f_data->cnt = pullup(&bp,f_data->data,fragsize);
  268.  
  269.         /* Put IP header back on */
  270.         if((tbp = htonip(&ip,f_data)) == NULLBUF){
  271.             free_p(f_data);
  272.             free_p(bp);
  273.             return -1;
  274.         }
  275.         /* and ship it out */
  276.         if((*iface->send)(tbp,iface,gateway,
  277.             precedence,delay,throughput,reliability) == -1)
  278.             return -1;
  279.  
  280.         offset += fragsize;
  281.         length -= fragsize;
  282.     }
  283.     return 0;
  284. }
  285.  
  286. struct rt_cache rt_cache;
  287.  
  288. /* Add an entry to the IP routing table. Returns 0 on success, -1 on failure */
  289. int
  290. rt_add(target,bits,gateway,metric,interface)
  291. int32 target;        /* Target IP address prefix */
  292. unsigned int bits;    /* Size of target address prefix in bits (0-32) */
  293. int32 gateway;
  294. int metric;
  295. struct interface *interface;
  296. {
  297.     struct route *rp,**hp,*rt_lookup();
  298.     int16 hash_ip(),i;
  299.     int32 mask;
  300.  
  301.     if(interface == NULLIF)
  302.         return -1;
  303.  
  304.     rt_cache.target = 0;    /* Flush cache */
  305.  
  306.     /* Zero bits refers to the default route */
  307.     if(bits == 0){
  308.         rp = &r_default;
  309.     } else {
  310.         if(bits > 32)
  311.             bits = 32;
  312.  
  313.         /* Mask off don't-care bits */
  314.         mask = 0xffffffff;
  315.         for(i=31;i >= bits;i--)
  316.             mask <<= 1;
  317.  
  318.         target &= mask;
  319.         /* Search appropriate chain for existing entry */
  320.         for(rp = routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  321.             if(rp->target == target)
  322.                 break;
  323.         }
  324.     }
  325.     if(rp == NULLROUTE){
  326.         /* The target is not already in the table, so create a new
  327.          * entry and put it in.
  328.          */
  329.         if((rp = (struct route *)malloc(sizeof(struct route))) == NULLROUTE)
  330.             return -1;    /* No space */
  331.         /* Insert at head of table */
  332.         rp->prev = NULLROUTE;
  333.         hp = &routes[bits-1][hash_ip(target)];
  334.         rp->next = *hp;
  335.         if(rp->next != NULLROUTE)
  336.             rp->next->prev = rp;
  337.         *hp = rp;
  338.     }
  339.     rp->target = target;
  340.     rp->gateway = gateway;
  341.     rp->metric = metric;
  342.     rp->interface = interface;
  343.  
  344.     return 0;
  345. }
  346.  
  347. /* Remove an entry from the IP routing table. Returns 0 on success, -1
  348.  * if entry was not in table.
  349.  */
  350. int
  351. rt_drop(target,bits)
  352. int32 target;
  353. unsigned int bits;
  354. {
  355.     register struct route *rp;
  356.     struct route *rt_lookup();
  357.     unsigned int i;
  358.     int16 hash_ip();
  359.     int32 mask;
  360.  
  361.     rt_cache.target = 0;    /* Flush the cache */
  362.  
  363.     if(bits == 0){
  364.         /* Nail the default entry */
  365.         r_default.interface = NULLIF;
  366.         return 0;
  367.     }
  368.     if(bits > 32)
  369.         bits = 32;
  370.  
  371.     /* Mask off don't-care bits */
  372.     mask = 0xffffffff;
  373.     for(i=31;i >= bits;i--)
  374.         mask <<= 1;
  375.  
  376.     target &= mask;
  377.  
  378.     /* Search appropriate chain for existing entry */
  379.     for(rp = routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  380.         if(rp->target == target)
  381.             break;
  382.     }
  383.     if(rp == NULLROUTE)
  384.         return -1;    /* Not in table */
  385.  
  386.     if(rp->next != NULLROUTE)
  387.         rp->next->prev = rp->prev;
  388.     if(rp->prev != NULLROUTE)
  389.         rp->prev->next = rp->next;
  390.     else
  391.         routes[bits-1][hash_ip(target)] = rp->next;
  392.  
  393.     free((char *)rp);
  394.     return 0;
  395. }
  396.  
  397. /* Compute hash function on IP address */
  398. static int16
  399. hash_ip(addr)
  400. register int32 addr;
  401. {
  402.     register int16 ret;
  403.  
  404.     ret = hiword(addr);
  405.     ret ^= loword(addr);
  406.     ret %= NROUTE;
  407.     return ret;
  408. }
  409. #ifndef    GWONLY
  410. /* Given an IP address, return the MTU of the local interface used to
  411.  * reach that destination. This is used by TCP to avoid local fragmentation
  412.  */
  413. int16
  414. ip_mtu(addr)
  415. int32 addr;
  416. {
  417.     register struct route *rp;
  418.     struct route *rt_lookup();
  419.     struct interface *iface;
  420.  
  421.     rp = rt_lookup(addr);
  422.     if(rp == NULLROUTE || rp->interface == NULLIF)
  423.         return 0;
  424.  
  425.     iface = rp->interface;
  426.     if(iface->forw != NULLIF)
  427.         return iface->forw->mtu;
  428.     else
  429.         return iface->mtu;
  430. }
  431. #endif
  432. /* Look up target in hash table, matching the entry having the largest number
  433.  * of leading bits in common. Return default route if not found;
  434.  * if default route not set, return NULLROUTE
  435.  */
  436. static struct route *
  437. rt_lookup(target)
  438. int32 target;
  439. {
  440.     register struct route *rp;
  441.     int16 hash_ip();
  442.     int bits;
  443.     int32 tsave;
  444.     int32 mask;
  445.  
  446.     if(target == rt_cache.target)
  447.         return rt_cache.route;
  448.  
  449.     tsave = target;
  450.  
  451.     mask = ~0;    /* All ones */
  452.     for(bits = 31;bits >= 0; bits--){
  453.         target &= mask;
  454.         for(rp = routes[bits][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  455.             if(rp->target == target){
  456.                 /* Stash in cache and return */
  457.                 rt_cache.target = tsave;
  458.                 rt_cache.route = rp;
  459.                 return rp;
  460.             }
  461.         }
  462.         mask <<= 1;
  463.     }
  464.     if(r_default.interface != NULLIF){
  465.         rt_cache.target = tsave;
  466.         rt_cache.route = &r_default;
  467.         return &r_default;
  468.     } else
  469.         return NULLROUTE;
  470. }
  471. /* Convert IP header in host format to network mbuf */
  472. struct mbuf *
  473. htonip(ip,data)
  474. struct ip *ip;
  475. struct mbuf *data;
  476. {
  477.     int16 hdr_len;
  478.     struct mbuf *bp;
  479.     register char *cp;
  480.     int16 checksum;
  481.  
  482.     hdr_len = IPLEN + ip->optlen;
  483.     if((bp = pushdown(data,hdr_len)) == NULLBUF){
  484.         free_p(data);
  485.         return NULLBUF;
  486.     }
  487.     cp = bp->data;
  488.     
  489.     *cp++ = (IPVERSION << 4) | (hdr_len >> 2);
  490.     *cp++ = ip->tos;
  491.     cp = put16(cp,ip->length);
  492.     cp = put16(cp,ip->id);
  493.     cp = put16(cp,ip->fl_offs);
  494.     *cp++ = ip->ttl;
  495.     *cp++ = ip->protocol;
  496.     cp = put16(cp,0);    /* Clear checksum */
  497.     cp = put32(cp,ip->source);
  498.     cp = put32(cp,ip->dest);
  499.     if(ip->optlen != 0)
  500.         memcpy(cp,ip->options,ip->optlen);
  501.  
  502.     /* Compute checksum and insert into header */
  503.     checksum = cksum(NULLHEADER,bp,hdr_len);
  504.     put16(&bp->data[10],checksum);
  505.  
  506.     return bp;
  507. }
  508. /* Extract an IP header from mbuf */
  509. int
  510. ntohip(ip,bpp)
  511. struct ip *ip;
  512. struct mbuf **bpp;
  513. {
  514.     char v_ihl;
  515.     int16 ihl;
  516.  
  517.     v_ihl = pullchar(bpp);
  518.     ip->version = (v_ihl >> 4) & 0xf;
  519.     ip->tos = pullchar(bpp);
  520.     ip->length = pull16(bpp);
  521.     ip->id = pull16(bpp);
  522.     ip->fl_offs = pull16(bpp);
  523.     ip->ttl = pullchar(bpp);
  524.     ip->protocol = pullchar(bpp);
  525.     (void)pull16(bpp);    /* Toss checksum */
  526.     ip->source = pull32(bpp);
  527.     ip->dest = pull32(bpp);
  528.  
  529.     ihl = (v_ihl & 0xf) << 2;
  530.     if(ihl < IPLEN){
  531.         /* Bogus packet; header is too short */
  532.         return -1;
  533.     }
  534.     ip->optlen = ihl - IPLEN;
  535.     if(ip->optlen != 0)
  536.         pullup(bpp,ip->options,ip->optlen);
  537.  
  538.     return ip->optlen + IPLEN;
  539. }
  540. /* Perform end-around-carry adjustment */
  541. int16
  542. eac(sum)
  543. register int32 sum;    /* Carries in high order 16 bits */
  544. {
  545.     register int16 csum;
  546.  
  547.     while((csum = sum >> 16) != 0)
  548.         sum = csum + (sum & 0xffffL);
  549.     return (int16) (sum & 0xffffl);    /* Chops to 16 bits */
  550. }
  551. /* Checksum a mbuf chain, with optional pseudo-header */
  552. int16
  553. cksum(ph,m,len)
  554. struct pseudo_header *ph;
  555. register struct mbuf *m;
  556. int16 len;
  557. {
  558.     register unsigned int cnt, total;
  559.     register int32 sum, csum;
  560.     register char *up;
  561.     int16 csum1;
  562.     int swap = 0;
  563.     int16 lcsum();
  564.  
  565.     sum = 0l;
  566.  
  567.     /* Sum pseudo-header, if present */
  568.     if(ph != NULLHEADER){
  569.         sum = hiword(ph->source);
  570.         sum += loword(ph->source);
  571.         sum += hiword(ph->dest);
  572.         sum += loword(ph->dest);
  573.         sum += uchar(ph->protocol);
  574.         sum += ph->length;
  575.     }
  576.     /* Now do each mbuf on the chain */
  577.     for(total = 0; m != NULLBUF && total < len; m = m->next) {
  578.         cnt = min(m->cnt, len - total);
  579.         up = (char *)m->data;
  580.         csum = 0;
  581.  
  582.         if(((long)up) & 1){
  583.             /* Handle odd leading byte */
  584.             if(swap)
  585.                 csum = uchar(*up++);
  586.             else
  587.                 csum = (int16)(uchar(*up++) << 8);
  588.             cnt--;
  589.             swap = !swap;
  590.         }
  591.         if(cnt > 1){
  592.             /* Have the primitive checksumming routine do most of
  593.              * the work. At this point, up is guaranteed to be on
  594.              * a short boundary
  595.              */
  596.             csum1 = lcsum((unsigned short *)up, cnt >> 1);
  597.             if(swap)
  598.                 csum1 = (csum1 << 8) | (csum1 >> 8);
  599.             csum += csum1;
  600.         }
  601.         /* Handle odd trailing byte */
  602.         if(cnt & 1){
  603.             if(swap)
  604.                 csum += uchar(up[--cnt]);
  605.             else
  606.                 csum += (int16)(uchar(up[--cnt]) << 8);
  607.             swap = !swap;
  608.         }
  609.         sum += csum;
  610.         total += m->cnt;
  611.     }
  612.     /* Do final end-around carry, complement and return */
  613.     return ~eac(sum) & 0xffff;
  614. }
  615. /* Machine-independent, alignment insensitive network-to-host long conversion */
  616. static int32
  617. get32(cp)
  618. register char *cp;
  619. {
  620.     int32 rval;
  621.  
  622.     rval = uchar(*cp++);
  623.     rval <<= 8;
  624.     rval |= uchar(*cp++);
  625.     rval <<= 8;
  626.     rval |= uchar(*cp++);
  627.     rval <<= 8;
  628.     rval |= uchar(*cp);
  629.  
  630.     return rval;
  631. }
  632.